package StringTest;

import java.util.Scanner;

/**
 * 对于字符串的比较，简单的可以用equals方法，但是对于本题这种
 * 频繁改变字符串，去判断另一个串是否与之相同
 * 这种题用普通的方法去做，一定是移动一次，比较一次
 * 因此想要简化，只能从移动和比较上入手
 * 移动就代表着时间复杂度，可不可以不移动
 * 比较就代表着浪费时间，可不可以少比较几次
 *
 * 因此使用contains方法是很好的优化，但是
 * contains方法的底层是暴力匹配算法
 * （为什么不用 KMP？
 * 性能考量：
 * KMP 需要 O(m) 的预处理时间（m 是模式串长度）
 * 对于短字符串（Java 中大多数场景），预处理开销可能超过收益
 * Java 团队经过测试发现暴力匹配在大多数实际场景中表现更好
 * 实际优化：
 * Java 的 indexOf() 实现使用了高度优化的本地代码（intrinsic）
 * 对短模式串有特殊优化（比如首字符优先匹配）
 * 对长字符串可能会使用 SIMD 指令加速）
 * 如果想要进一步优化
 * 则可以使用KMP算法去优化比较过程
 */
public class Demo2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String A = sc.nextLine();
        String B = sc.nextLine();
        System.out.println(move(A, B));
    }
    public static boolean move(String A,String B){
        if(A.length()!=B.length()){
            return false;
        }
        if(A.isEmpty()){
            return true;
        }
        //return (A+A).contains(B);
        return kmpSearch(A + A, B) != -1;
    }
    // KMP算法实现
    private static int kmpSearch(String text, String pattern) {
        int[] lps = computeLPSArray(pattern);
        int i = 0; // text的索引
        int j = 0; // pattern的索引

        while (i < text.length()) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                if (j == pattern.length()) {
                    return i - j; // 找到匹配
                }
            } else {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return -1; // 未找到
    }

    // 计算LPS数组(最长前缀后缀)
    private static int[] computeLPSArray(String pattern) {
        int[] lps = new int[pattern.length()];
        int len = 0; // 当前最长前缀后缀长度
        int i = 1;

        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }
}
